package com.db.collections;

/**
 * This class represents realization of hashMap for primitive type int with linear open addressing
 *
 * @author Alexander Kotov (kotov.alex.22@gmail.com)
 */
public class IntHashMap2 {

    /**
     * The default initial capacity - MUST be a power of two.
     */
    private static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

    /**
     * The maximum capacity, used if a higher value is implicitly specified
     * by either of the constructors with arguments.
     * MUST be a power of two <= 1<<30.
     */
    private static final int MAXIMUM_CAPACITY = 1 << 30;

    /**
     * The multiplier for calculate new capacity while increasing map
     */
    private static final int CAPACITY_MULTIPLIER = 2;

    /**
     * The load factor used when none specified in constructor.
     */
    private static final float DEFAULT_LOAD_FACTOR = 0.75f;

    /**
     * The number of key-value mappings contained in this map.
     */
    transient private int size;

    /**
     * The load factor for the hash table.
     *
     * @serial
     */
    private final float loadFactor;

    /**
     * The initial capacity of the hash table.
     *
     * @serial
     */
    final private int initialCapacity;

    private int[] keys;

    private int[] values;

    private int capacity;

    private int zeroElement;

    private boolean containsZeroElement;

    /**
     * Constructs an empty <tt>IntHashMap2</tt> with the specified initial with collisions chains
     * capacity and load factor.
     *
     * @param initialCapacity the initial capacity
     * @param loadFactor      the load factor
     * @throws IllegalArgumentException if the initial capacity is negative
     *                                  or the load factor is nonpositive or more than 1
     */
    public IntHashMap2(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY) {
            throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
        } else {
            this.initialCapacity = initialCapacity;
        }
        if (loadFactor <= 0 || Float.isNaN(loadFactor) || loadFactor > 1)
            throw new IllegalArgumentException("Illegal load factor: " + loadFactor);

        this.loadFactor = loadFactor;
        clear();
    }

    /**
     * Constructs an empty <tt>IntHashMap2</tt> with the specified initial
     * capacity and the default load factor (0.75).
     *
     * @param initialCapacity the initial capacity.
     * @throws IllegalArgumentException if the initial capacity is negative.
     */
    public IntHashMap2(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

    /**
     * Constructs an empty <tt>IntHashMap2</tt> with the default initial capacity
     * (16) and the default load factor (0.75).
     */
    public IntHashMap2() {
        this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
    }

    /**
     * @param K specified key
     * @return the value to which the specified key is mapped,
     * or <tt>null</tt> if this map contains no mapping for the key.
     */
    public Integer get(int K) {
        if (K != 0) {
            for (int i = 0; i < capacity; ++i) {
                int probeIndex = (K + i) % capacity;
                if (keys[probeIndex] == K) {
                    return values[probeIndex];
                }
            }
            return null;
        } else {
            return (containsZeroElement) ? zeroElement : null;
        }
    }

    /**
     * Associates the specified value with the specified key in this map.
     * If the map previously contained a mapping for the key, the old
     * value is replaced.
     *
     * @param K key with which the specified value is to be associated
     * @param V value to be associated with the specified key
     * @return the previous value associated with <tt>K</tt>, or
     *         <tt>null</tt> if there was no mapping for <tt>K</tt>.
     */
    public Integer put(int K, int V) {
        if (K != 0) {
            if (needResize()) {
                resize(CAPACITY_MULTIPLIER * capacity);
            }
            return placeToMap(K, V);
        } else {
            boolean oldContainsZeroElement = containsZeroElement;
            int oldZeroElement = zeroElement;
            containsZeroElement = true;
            zeroElement = V;
            if (!oldContainsZeroElement) {
                size++;
            }
            return (oldContainsZeroElement) ? oldZeroElement : null;
        }
    }

    /**
     * Removes all of the mappings from this map.
     * The map will be empty after this call returns.
     */
    public void clear() {
        containsZeroElement = false;
        clear(initialCapacity);
    }

    /**
     * @return the number of key-value mappings contained in this map.
     */
    public int size() {
        return size;
    }

    /**
     * @param K key
     * @return true if map contains element with key K,
     *         false otherwise.
     */
    public boolean contains(int K) {
        if (K != 0) {
            for (int i = 0; i < capacity; ++i) {
                int probeIndex = (K + i) % capacity;
                if (keys[probeIndex] == K) {
                    return true;
                }
            }
            return false;
        } else {
            return containsZeroElement;
        }
    }

    private void resize(int newCapacity) {
        int oldCapacity = capacity;
        int[] curKeys = keys;
        int[] curValues = values;

        clear(newCapacity);

        for (int i = 0; i < oldCapacity; ++i) {
            if (curKeys[i] != 0) {
                placeToMap(curKeys[i], curValues[i]);
            }
        }

        if (containsZeroElement) {
            size++;
        }
    }

    private Integer placeToMap(int K, int V) {
        for (int i = 0; i < capacity; ++i) {
            int probeIndex = (K + i) % capacity;
            if (keys[probeIndex] == 0) {
                keys[probeIndex] = K;
                values[probeIndex] = V;
                size++;
                return null;
            }
            if (keys[probeIndex] == K) {
                int result = values[probeIndex];
                values[probeIndex] = V;
                return result;
            }
        }
        return null;
    }

    private void clear(int initCapacity) {
        capacity = initCapacity;
        keys = new int[capacity];
        values = new int[capacity];
        size = 0;
    }

    private boolean needResize() {
        return size >= (int) (loadFactor * capacity);
    }
}

